A recursive function needs base cases and recursive steps.
- Base Case 1: If the current node is None, we've hit a dead end. The key is not in the tree, so we return False.
- Base Case 2: If the current node's key matches the target key, we've found it! We return True.
- Recursive Step: If neither base case is met, compare keys. If the target key is smaller, call find on the left child; otherwise, on the right child. Return the result up the call stack.
# Node class is the same as in Solution 1.
def find(node, key):
"""Searches for a key in the BST recursively."""
# Base Case 1: We've hit a dead end.
if node is None:
return __________
# Base Case 2: We've found the key.
if key == node.key:
return __________
# Recursive Step: Search in the correct subtree.
if key < node.key:
return find(__________, key)
else:
return find(__________, key)
Copied!